#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/8/3 21:13
# @USER    : Shengji He
# @File    : Search2DMatrix.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        """
        Write an efficient algorithm that searches for a value in an m x n matrix.
        This matrix has the following properties:
            - Integers in each row are sorted from left to right.
            - The first integer of each row is greater than the last integer of the previous row.
        Example 1:
            Input:
                matrix =
                    [
                        [1,   3,  5,  7],
                        [10, 11, 16, 20],
                        [23, 30, 34, 50]
                    ]
                target = 3
            Output: true
        Example 2:
            Input:
                matrix =
                    [
                        [1,   3,  5,  7],
                        [10, 11, 16, 20],
                        [23, 30, 34, 50]
                    ]
                target = 13
            Output: false

        :param matrix:
        :param target:
        :return:
        """
        if not matrix or not matrix[0]:
            return False
        rows = len(matrix)
        columns = len(matrix[0])
        r = 0
        while r <= rows - 1:
            if matrix[r][0] <= target <= matrix[r][columns - 1]:
                for c in range(columns):
                    if matrix[r][c] == target:
                        return True
                    elif matrix[r][c] > target:
                        return False
                    else:
                        pass
            else:
                r += 1
        return False


if __name__ == '__main__':
    S = Solution()
    matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]
    targrt = 13
    print(S.searchMatrix(matrix, targrt))
    print('done')
